1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <cstdio>
#include <cstdlib>
#include <algorithm>
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
struct T{
#define S(d) a[a[cur].son[d]]
struct A{
int son[2], v, sz, lnk, rd;
}a[maxn << 1]; int tot;
T(){tot = 0;}
void pushup(int cur){
a[cur].sz = S(0).sz + S(1).sz + a[cur].v;
}
void rotate(int &cur, int d){
int k = a[cur].son[d ^ 1];
a[cur].son[d ^ 1] = a[k].son[d];
a[k].son[d] = cur;
pushup(cur); pushup(k);
cur = k;
}
void ins(int &cur, int x){
if (!cur){
cur = ++tot;
a[cur].sz = a[cur].v = 1;
a[cur].lnk = x;
a[cur].rd = rand();
return;
}
if (a[cur].lnk == x){
a[cur].v++; a[cur].sz++;
return;
}
int d = (x > a[cur].lnk);
ins(a[cur].son[d], x);
if (a[cur].rd < S(d).rd) rotate(cur, d ^ 1);
pushup(cur);
}
void del(int &cur, int x){
if (!cur) return;
if (x < a[cur].lnk) del(a[cur].son[0], x);
else if (x > a[cur].lnk) del(a[cur].son[1], x);
else{
if (a[cur].v > 1){
a[cur].v--;
a[cur].sz--;
}
else if (!a[cur].son[0] && !a[cur].son[1]){
a[cur].sz--;
if (--a[cur].v == 0) cur = 0;
}
else if (a[cur].son[0] && !a[cur].son[1]){
rotate(cur, 1);
del(a[cur].son[1], x);
}
else if (!a[cur].son[0] && a[cur].son[1]){
rotate(cur, 0);
del(a[cur].son[0], x);
}
else{
int d = (S(0).rd > S(1).rd);
rotate(cur, d);
del(a[cur].son[d], x);
}
}
pushup(cur);
}
int rank(int cur, int x){
if (!cur) return 0;
if (a[cur].lnk == x) return S(0).sz + 1;
if (a[cur].lnk < x) return S(0).sz + a[cur].v + rank(a[cur].son[1], x);
if (a[cur].lnk > x) return rank(a[cur].son[0], x);
}
int find(int cur, int x){
if (!cur) return 0;
if (S(0).sz >= x) return find(a[cur].son[0], x);
else if (S(0).sz + a[cur].v >= x) return a[cur].lnk;
else return find(a[cur].son[1], x - S(0).sz - a[cur].v);
}
int pre(int cur, int x){
if (!cur) return -INF;
if (a[cur].lnk >= x) return pre(a[cur].son[0], x);
return max(a[cur].lnk, pre(a[cur].son[1], x));
}
int suf(int cur, int x){
if (!cur) return INF;
if (a[cur].lnk <= x) return suf(a[cur].son[1], x);
return min(a[cur].lnk, suf(a[cur].son[0], x));
}
}t; int Q, rt;
int main(){
scanf("%d", &Q);
while (Q--){
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == 1) t.ins(rt, x);
if (opt == 2) t.del(rt, x);
if (opt == 3) printf("%d\n", t.rank(rt, x));
if (opt == 4) printf("%d\n", t.find(rt, x));
if (opt == 5) printf("%d\n", t.pre(rt, x));
if (opt == 6) printf("%d\n", t.suf(rt, x));
}
return 0;
}
|